<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML 2.0//EN">
<html><head>
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
<!--Converted with LaTeX2HTML 96.1 (Feb 5, 1996) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds -->


<title>Power of Cryptography</title>
<meta name="description" content="Power of Cryptography">
<meta name="keywords" content="htmlatex">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<link rel="STYLESHEET" href="acm-00113_files/htmlatex.css">
</head><body bgcolor="#ffffff" lang="EN">
 <h1><br clear="all"><center><table bgcolor="#0060f0"><tbody><tr><td><b><font size="5" color="#c0ffff">&nbsp;<a name="SECTION0001000000000000000000">Power of Cryptography</a></font>&nbsp;</b></td></tr></tbody></table></center></h1>
<p>
</p><h2><font color="#0070e8"><a name="SECTION0001001000000000000000">Background</a></font></h2>
<p>
Current work in cryptography involves (among other things) large prime
numbers and computing powers of numbers modulo functions of these
primes.  Work in this area has resulted in the practical use of results
from number theory and other branches of mathematics once considered to
be of only theoretical interest.
</p><p>
This problem involves the efficient computation of integer roots of
numbers.
</p><p>
</p><h2><font color="#0070e8"><a name="SECTION0001002000000000000000">The Problem</a></font></h2>
<p>
Given an integer  <img alt="tex2html_wrap_inline32" src="acm-00113_files/113img1.gif" width="41" align="middle" height="25">  and an integer  <img alt="tex2html_wrap_inline34" src="acm-00113_files/113img2.gif" width="41" align="middle" height="25">  you are to write a
program that determines  <img alt="tex2html_wrap_inline36" src="acm-00113_files/113img3.gif" width="22" align="middle" height="25"> , the positive  <img alt="tex2html_wrap_inline38" src="acm-00113_files/113img4.gif" width="26" align="bottom" height="18">  root
of <i>p</i>.  In this problem, given such integers <i>n</i> and <i>p</i>, <i>p</i> will
always be of the form  <img alt="tex2html_wrap_inline48" src="acm-00113_files/113img5.gif" width="17" align="bottom" height="12">  for an integer <i>k</i> (this integer is what
your program must find).
</p><p>
</p><h2><font color="#0070e8"><a name="SECTION0001003000000000000000">The Input</a></font></h2>
<p>
The input consists of a sequence of integer pairs <i>n</i> and <i>p</i> with each
integer on a line by itself.  For all such pairs  <img alt="tex2html_wrap_inline56" src="acm-00113_files/113img6.gif" width="91" align="middle" height="25"> ,
 <img alt="tex2html_wrap_inline58" src="acm-00113_files/113img7.gif" width="100" align="middle" height="30">  and there exists an integer <i>k</i>,  <img alt="tex2html_wrap_inline62" src="acm-00113_files/113img8.gif" width="88" align="middle" height="30">  such that  <img alt="tex2html_wrap_inline64" src="acm-00113_files/113img9.gif" width="50" align="middle" height="25"> .
</p><p>
</p><h2><font color="#0070e8"><a name="SECTION0001004000000000000000">The Output</a></font></h2>
<p>
For each integer pair <i>n</i> and <i>p</i> the value  <img alt="tex2html_wrap_inline36" src="acm-00113_files/113img3.gif" width="22" align="middle" height="25">  should be printed,
i.e., the number <i>k</i> such that  <img alt="tex2html_wrap_inline64" src="acm-00113_files/113img9.gif" width="50" align="middle" height="25"> .
</p><p>
</p><h2><font color="#0070e8"><a name="SECTION0001005000000000000000">Sample Input</a></font></h2>
<p>
</p><pre>2
16
3
27
7
4357186184021382204544</pre>
<p>
</p><h2><font color="#0070e8"><a name="SECTION0001006000000000000000">Sample Output</a></font></h2>
<p>
</p><pre>4
3
1234</pre>
<p>
</p></body></html>